class Heap {
  constructor(array) {
    this.array = array
  }

  upAdjust() {
    // 上浮调整
    let childIndex = this.array.length - 1;
    let parentIndex = Math.floor((childIndex - 1)/2);
    let temp = this.array[childIndex];
    while (childIndex > 0 && temp < this.array[parentIndex]) {
      this.array[childIndex] = this.array[parentIndex];
      childIndex = parentIndex;
      parentIndex = Math.floor((parentIndex - 1)/2);
    }
    this.array[childIndex] = temp;
    return this.array;
  }

  downAdjust(arr, parentIndex, leng) {
    // 下沉调整
    let temp = arr[parentIndex]; // 父节点的值
    let childIndex = 2 * parentIndex + 1; // 孩子节点下标,默认是左孩子
    while(childIndex < leng) {
      // childIndex + 1 为右孩子节点下标
      if (childIndex + 1 < leng && arr[childIndex + 1]) {
        // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
        childIndex++;
      }
      if (temp <= arr[childIndex]) {
        break;
      }
      arr[parentIndex] = arr[childIndex];
      parentIndex = childIndex;
      childIndex = 2 * childIndex +1;
    }
  }

  buildHeap() {
    // 构建堆

    // 从最后一个非叶子节点开始，依次做下沉调整
    for(let i = Math.floor((this.array.length - 2)/2); i >= 0; i--) {
      this.downAdjust(this.array, i, this.array.length);
    }
    return this.array;
  }
}